1. Field of the Invention
Embodiments of the present invention relate to data processing. More particularly, embodiments of the present invention relate to determining the median value of a frame of video data utilizing a field programmable gate array system.
2. Description of the Related Art
A digital video image generally comprises a plurality of picture elements, commonly known as pixels, that are arranged in an array. For common video applications, such as television or digital photography, the array of pixels is rectangular and may be expressed as X×Y, although square arrays are also possible. The entire array of pixels may be known as a frame. Each pixel in the frame may possess one or more video characteristic values, such as a brightness value or a color value. In order to further process the video image data for one or more objects of interest within the frame, it is usually necessary to isolate the objects. The median of the characteristic value of all the pixels within the frame may be used to isolate the objects.
Traditional approaches to determining the median have required that the characteristic values of all the pixels in the frame be sorted in either ascending or descending order. In this case, the sort creates an array of X×Y elements, each with a characteristic value. If X×Y=N, then the array includes N elements, each with a characteristic value. As is commonly known in statistics, the median is the value of the N/2 sorted element; or the higher, the lower, or the average of two potential median values if the array contains an even number of elements. This type of sort may take a time on the order of N·log(N). Using traditional computer processing techniques, wherein tasks may be performed in software executed in a serial fashion, the sort may take longer than it takes to capture one frame of video data, particularly as N gets large. Furthermore, moving image video requires that many successive frames of video data are captured every second (standard rates include 24 frames per second (fps), 30 fps, and 120 fps). A problem may occur if a first frame of video data is not sorted by the time a second frame of data is captured and ready for sort. Data may be lost and errors may occur, with the result that performance may be sacrificed. Therefore, in order to avoid or reduce errors, fewer frames of data may be sorted, such as every second or third frame of data.